3.2 队列

队列与栈有相同的地方，但是也略有不同。本节我们将讲解队列的基本概念及Go语言实现。

本节代码存放目录为 lesson5

概念及原理

队列是一种线性数据结构，它遵循先进先出（FIFO, First In First Out）的原则。

也就是说，第一个进入队列的元素会最先被移除。

队列的操作包括：

• 入队（Enqueue）：将元素加入队列的尾部。

• 出队（Dequeue）：从队列的头部移除元素。

• 查看队首元素（Peek）：获取队列头部的元素但不移除它。

队列就像排队一样，第一个排队的人最先离开，而新加入队列的人在最后排队。

队列的插入操作只能在队尾进行，删除操作只能在队首进行，非常适合处理需要按顺序处理的任务。

队列的结构示意图如下所示：

队首                          队尾
+-------+    +-------+    +-------+
|   1   | <- |   2   | <- |   3   |
+-------+    +-------+    +-------+
出队方向 <-                   <- 入队方向

• 入队（Enqueue）：将元素 3 加入队尾。

• 出队（Dequeue）：移除队首元素 1。

• 查看队首元素（Peek）：获取队首元素 1，但不移除它。

其操作示意如下所示：

• 入队操作：将元素依次加入队尾。

队首                          队尾
+-------+
|   1   |
+-------+

+-------+    +-------+
|   1   | <- |   2   |
+-------+    +-------+

+-------+    +-------+    +-------+
|   1   | <- |   2   | <- |   3   |
+-------+    +-------+    +-------+

• 出队操作：从队首依次移除元素。

队首                    队尾
+-------+    +-------+    +-------+
|   1   | <- |   2   | <- |   3   |
+-------+    +-------+    +-------+

+-------+    +-------+
|   2   | <- |   3   |
+-------+    +-------+

+-------+
|   3   |
+-------+

队列在很多应用中都有广泛的使用，特别是在需要按顺序处理的任务中：

• 任务调度：操作系统或任务调度器使用队列来管理任务，按顺序执行任务。

• 消息队列：在消息传递系统中，消息通常按照队列的顺序被处理和传递。

• 广度优先搜索（BFS）：在图或树的遍历中，队列用于按层次逐步访问节点。

• 缓存管理：队列常用于缓存系统的缓存替换策略（如FIFO缓存算法）。

Go语言的实现

在Go语言中，通道channel与队列是有一些类似的，但是也不能算作一个完整的队列。

接下来我们同样使用切片模拟队列的实现，主要包括入队、出队、查看队首元素等，代码如下所示：

type Queue struct {
    elements []int
}

func (q *Queue) Enqueue(ele int) {
    q.elements = append(q.elements, ele)
}

func (q *Queue) Dequeue() int {
    if len(q.elements) == 0 {
        fmt.Println("队列为空")
        return -1
    }
    front := q.elements[0]
    // 移除队首元素
    q.elements = q.elements[1:]
    return front
}

func (q *Queue) Peek() int {
    if len(q.elements) == 0 {
        fmt.Println("队列为空")
        return -1
    }
    return q.elements[0]
}

func (q *Queue) IsEmpty() bool {
    return len(q.elements) == 0
}

func main() {
    queue := &Queue{}
    fmt.Println("queue is empty-> ", queue.IsEmpty())
    queue.Enqueue(1)
    queue.Enqueue(2)
    queue.Enqueue(3)

    queue.Dequeue()
    fmt.Println("queue peek-> ", queue.Peek())
}

结果输出如下所示：

queue is empty->  true
queue peek->  2

在上面的代码中，我们通过切片实现了队列的操作，将数组的头部作为队列的头部，添加元素则自动加到数组的末尾，也就是队列的尾部。

在实际的开发过程中，我们可以再增加上锁，即实现了一个支持并发的队列结构。

小结

队列是一种重要的数据结构，它遵循先进先出的原则，同样比较适合按顺序处理的任务场景，与栈结构大同小异。

关于本节总结如下：

• 队列是一种FIFO结构，最先入队的元素最先出队。

• 所有的插入操作都在队尾进行，删除操作在队首进行。

• 队列在处理需要顺序执行的任务时表现良好，适合调度、广度优先搜索等场景。